package org.example.myleet.p1579;

public class Solution {
    /**
     * 16 ms
     * 优先将公共边加入并查集中，并发现多余的边，然后将并查集复制给Alice和Bob，继续将非公共边分别加入到对应到并查集中，并发现剩余的多余边
     * 最后检查并查集是否完全连通，如果都是完全连通，则统计多余边，即为最多可以移除的边
     */
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        //先将公共边加入并查集中
        UnionFind uf = new UnionFind(n);
        for (int[] ints : edges) {
            if (ints[0] == 3) {
                uf.union(ints[1], ints[2]);
            }
        }
        //从公共边加入过程中得到多余的边数
        int sharedRedundantCount = uf.redundantEdge;
        //复制并查集
        UnionFind ufAlice = new UnionFind(uf.parent, 0);
        UnionFind ufBob = new UnionFind(uf.parent, 0);
        for (int[] edge : edges) {
            if (edge[0] == 1) {
                //Alice的边给Alice的并查集处理
                ufAlice.union(edge[1], edge[2]);
            } else if (edge[0] == 2) {
                //Bob的边给Bob的并查集处理
                ufBob.union(edge[1], edge[2]);
            }
        }
        if (ufAlice.isFullConnected() && ufBob.isFullConnected()) {
            //如果都是连通的，统计多余边数
            return sharedRedundantCount + ufAlice.redundantEdge + ufBob.redundantEdge;
        }
        return -1;
    }

    static class UnionFind {
        int[] parent;
        int redundantEdge;

        public UnionFind(int len) {
            int l = len+1;
            parent = new int[l];
            for (int i=0; i<l; i++) {
                parent[i] = i;
            }
            redundantEdge = 0;
        }

        public UnionFind(int[] parent, int redundantEdge) {
            this.parent = new int[parent.length];
            //深拷贝并查集
            System.arraycopy(parent, 0, this.parent, 0, parent.length);
            this.redundantEdge = redundantEdge;
        }

        public int find(int x) {
            int p = parent[x];
            if (p != parent[p]) {
                parent[x] = find(p);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                //两个节点已经通过某种路径连通了，则此边是多余的
                ++redundantEdge;
                return;
            }
            //两个点未连通，将两个点的根节点连起来
            parent[rootX] = rootY;
        }

        public boolean isFullConnected() {
            int p = find(1);
            for (int i=2; i<parent.length; i++) {
                if (p != find(i)) {
                    //根节点都一致时为全连通，有一个对不上都不是全连通
                    return false;
                }
            }
            return true;
        }
    }
}
